The present invention relates to techniques for detecting and correcting errors on storage media, and more particularly, to techniques for detecting and correcting errors on storage media using multiple interleave erasure pointers in a multi-level integrated interleave format.
Data bytes are stored on magnetic media in groups referred to as codewords (sectors). Typically, 512 data bytes are stored in each codeword. The codewords of data bytes may include multiple interleaved words (i.e., data byte strings or vectors) and corresponding check bytes that are byte interleaved.
Multibyte errors are detected and corrected in long byte strings recorded on a storage medium in blocks. Each block comprises a plurality of codewords and a plurality of block-level check bytes derived from the codewords. Each codeword includes data bytes and codeword check bytes mapped from a plurality of equal-length data byte strings according to a linear error correction code.
Each block is generated and recorded by logically summing the data byte strings and by mapping the logical sum and the data byte strings into counterpart codewords. The counter part codewords include codeword check bytes in accordance with the same linear error correction code. Next, the codewords are logically summed. The codewords and their logical sum are interleaved in a predetermined pattern prior to being recorded on a storage device or the like.
Additional details of a technique for detecting and correcting error bytes is discussed in U.S. Pat. No. 5,946,328, which is incorporated by reference herein. Three data streams m1(x), m2(x), and m3(x) are used as an example. Two of the data streams m1(x) and m2(x) are encoded by a first Reed-Solomon (RS) linear encoder that produces respective codewords c1(x) and c2(x). This first RS encoder appends 2t1 check bytes to each of the codewords.
The third datastream m3(x) is modified to form the logical (modulo 2) sum of m1(x)+m2(x)+m3(x) prior to encoding by a second RS encoder. This second RS encoder includes 2t1+2t2 check bytes within a codeword c′(x) of the logically-summed datastream. The codeword c3(x) represents the logical sum of the three codewords c1(x)+c2(x)+c′(x). The third codeword c3(x) contains 2t2 shared block check bytes and 2t1 individual check bytes when generated in this manner. The block check bytes are inside and an intrinsic part of the RS codeword.
Two of the codewords c1(x) and c2(x) are generated by linear error correction encoding of respective data byte strings m1(x) and m2(x). Codewords c1(x) and c2(x) require 2t1 check bytes. The codeword c′(x) are also generated by the linear encoding of the modulo 2 sum of m1(x), m2(x), and m3(x). Codeword c′(x) requires 2t1+2t2 check bytes. Data byte strings m1(x) and m2(x) are appended with 2t2 zeroes denoted by φ(x) in order to secure equal codeword length. The codeword outputs may then be expressed as:c1(x)=x2t1+2t2m1(x)+φ(x)+r1(x)c2(x)=x2t1+2t2m2(x)+φ(x)+r2(x)c′(x)=x2t1+2t2[m1(x)+m2(x)+m3(x)]+r(x)
The codeword c′(x) is further processed to produce a modified and third codeword c3 (x) by summing the three codewords c1(x), c2(x), and c′(x) modulo 2 such that:c3(x)=[c1(x)+c2(x)]+c′(x)=x2t1+2t2m3(x)+rB(x)+r3(x)
The check bytes rB(x) are the block check bytes shared by m1(x), m2(x), and m3(x), whereas r3(x) are the individual check bytes of data stream m3(x).
The check bytes r1(x), r2(x), and r3(x) are first level check bytes. These check bytes can only be used to correct t, errors in data bytes within codewords c1(x), c2(x), c3(x), respectively. The check bytes rB(x) in codeword c3(x) are second (block) level check bytes that can be used to correct t1+t2 data byte errors in any one of codewords c1(x), c2(x), and c3(x).
Following these computations, an integrated interleaved block of codewords c1(x), c2(x), and c3(x) is written out to the disk. Subsequently, when the disk must execute a read or read modify write command or the like, an addressed block or blocks of codewords are streamed from their track locations on the disk. Any errors on the disk are detected and corrected on the fly based on the syndrome processing of the codewords. The syndromes are derived from the purported codewords and their logical sum modulo 2. A non-zero syndrome indicates an error byte. Any nonzero syndromes are identified and processed over the codewords to correct the bytes in error. The updated block-level nonzero syndromes are also processed to locate and correct bytes in error in any single codeword that exceeds the correction capability of that codeword.
U.S. Pat. No. 6,275,965, which is incorporated herein by reference, describes a system that corrects error bytes in a two-level code structure. Up to a maximum of t1 error bytes in a codeword can be located and corrected using 2t1 check bytes per codeword. A codeword with error bytes exceeding its t1 codeword correction capacity is a bursty subblock. Up to a maximum of t1+t2 error bytes can be located and corrected in as many as B bursty subblocks using B*(2t2) block-level check bytes.
A post-encoding process is provided to “de-interleave” or redistribute the computed codewords into modified codewords such that the data vectors and their codeword check bytes are located in the same codeword. The block-level check bytes are distributed among the codewords.
The techniques described in the '965 patent are useful for correcting error bytes that occur in random locations with the codewords. However, the number of error bytes in the codewords can exceed the correction capability of the techniques described in the '965 patent. These types of errors are referred to as burst errors. Burst errors can occur, for example, as the result of a scratch or defect on a magnetic disk.
Therefore, it would be desirable to provide additional techniques for detecting and correcting burst errors occurring in data bytes that are formed in a two-level block code structure.